import java.util.*;

/**
* @description: 721. 账户合并
* @author hewei
* @date 2022/8/17 15:17
* @version 1.0
*/

public class AccountsMerge {

    public List<List<String>> accountsMerge1(List<List<String>> accounts) {
        HashMap<String, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            for (int j = 1; j < accounts.get(i).size(); j++) {
                String s = accounts.get(i).get(j);
                if (!map.containsKey(s)) map.put(s, new ArrayList<>());
                map.get(s).add(i);
            }
        }
        Deque<Integer> queue = new LinkedList<>();
        List<List<String>> ans = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        boolean[] flag = new boolean[accounts.size()];
        List<String> nameList = new ArrayList<>();
        for (int i = 0; i < accounts.size(); i++) {
            if (flag[i]) continue;
            queue.add(i);
            flag[i] = true;
            ans.add(new ArrayList<>());
            ans.get(ans.size() - 1).add("");
            nameList.add(accounts.get(i).get(0));
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                List<String> list = accounts.get(poll);
                for (int j = 1; j < list.size(); j++) {
                    String s = list.get(j);
                    if (!set.contains(s)) {
                        if (map.containsKey(s)) {
                            for (Integer integer : map.get(s)) {
                                if (!flag[integer]) queue.push(integer);
                                flag[integer] = true;
                            }
                        }
                        set.add(s);
                        ans.get(ans.size() - 1).add(s);
                    }
                }
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            List<String> list = ans.get(i);
            Collections.sort(list);
            list.set(0, nameList.get(i));
        }
        return ans;
    }

    class Union {
        int[] parents;

        public Union(int n) {
            parents = new int[n];
            Arrays.fill(parents, -1);
        }

        public int find(int i) {
            if (parents[i] == -1) {
                parents[i] = i;
                return i;
            }

            while (parents[i] != i) {
                parents[i] = parents[parents[i]];
                i = parents[i];
            }
            return i;
        }

        public void merge(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x == y) return;
            parents[y] = x;
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int count = 0;
        HashMap<String, Integer> map = new HashMap<>();
        HashMap<Integer, String> nameMap = new HashMap<>();
        List<String> nameList = new ArrayList<>();
        HashMap<Integer, String> reveresMap = new HashMap<>();
        for (List<String> account : accounts) {
            for (int i = 1; i < account.size(); i++) {
                String s = account.get(i);
                if (!map.containsKey(s)) {
                    map.put(s, count);
                    reveresMap.put(count, s);
                    nameMap.put(count, account.get(0));
                    ++count;
                }
            }
        }
        Union union = new Union(count);
        for (List<String> account : accounts) {
            if (account.size() == 2) {
                union.find(map.get(account.get(1)));
            } else
            for (int i = 2; i < account.size(); i++) {
                union.merge(map.get(account.get(1)), map.get(account.get(i)));
            }
        }
        List<List<String>> ans = new ArrayList<>();
        HashMap<Integer, List<String>> res = new HashMap<>();
        int[] parents = union.parents;
        for (int i = 0; i < parents.length; i++) {
            int temp = union.find(i);
            if (!res.containsKey(temp)) res.put(temp, new ArrayList<>());
            res.get(temp).add(reveresMap.get(i));
        }
        for (Map.Entry<Integer, List<String>> entry : res.entrySet()) {
            nameList.add(nameMap.get(entry.getKey()));
            List<String> list = new ArrayList<>();
            list.add("");
            list.addAll(entry.getValue());
            ans.add(list);
        }
        for (int i = 0; i < ans.size(); i++) {
            List<String> list = ans.get(i);
            Collections.sort(list);
            list.set(0, nameList.get(i));
        }
        return ans;
    }
}
